1. Field of the Invention
The present invention relates, in general, to the field of memory resource management in computer systems, more specifically to an improved method and apparatus for allocation and replacement of associative storage resources (e.g., cache lines and buffers).
2. Description of the Related Art
Conventional systems utilize computer and other data processing systems implemented in “hardware” often employ arrays of storage buffers and registers for local high-speed access to the contents by processes or “agents”. Since these resources are limited in size and amount, methods are employed to constantly reallocate the resources to meet the changing demands of competing agents. Most often these resources hold information for a short time for a given agent, before the resource is reallocated to accommodate new demands.
Associative hardware resource management techniques and algorithms address the tradeoff between speed and both cost and complexity, while functioning to use available resources as efficiently as possible. The least recently used (LRU) algorithm is commonly used to manage a limited set of associative resources within a partition. The algorithm suggests reallocating the least recently used resource to a current or pending demand. However, when multiple agents via for resources within the same resource partition, it is possible for one or more agents to monopolize the resource set, thereby causing competing agents to repeatedly reallocate each others resources before they have had sufficient use of a resource. This “thrashing” can significantly degrade system performance as agents waste proportionally significant time waiting for a resource. This situation is particularly evident when managing the fully associative “open pages” within “virtual channel” SDRAM, where address ranges or “pages” are held in buffers within the SDRAM devices for high speed reference. Dividing a resource into multiple partitions can segregate potentially monopolistic agents from each other. However, this scheme can waste resources when an agent fails to use/need all the resources within its partition. Therefore, a need exists for dynamically reallocating resources from underutilized partitions to highly utilized partitions.